package LeetCode._02算法基础.day08广度深度优先搜索;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 20 - 16:43
 * @Description 给你一个有n个节点的 有向无环图（DAG），
 * 请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
 * graph[i]是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点graph[i][j]存在一条有向边）。
 * @Version 中等
 */
public class _797所有可能的路径 {
    static int[][] graph = {
            {1, 2},
            {3},
            {3},
            {}
    };
    @Test
    public void test(){

    }
    /* by me 深度优先搜索 */
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        dfs(graph, 0);
        return res;
    }
    public void dfs(int[][] graph, int i){
        if(i == graph.length - 1){
            list.add(i);
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
        }
        list.add(i);
        //所有可选的下个节点
        for(int j = 0; j < graph[i].length; j++){
            dfs(graph, graph[i][j]);
        }
        //回溯
        list.remove(list.size() - 1);
    }

}
